import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
 * @lc app=leetcode.cn id=22 lang=java
 *
 * [22] 括号生成
 *
 * https://leetcode-cn.com/problems/generate-parentheses/description/
 *
 * algorithms
 * Medium (72.19%)
 * Likes:    591
 * Dislikes: 0
 * Total Accepted:    50.2K
 * Total Submissions: 69.5K
 * Testcase Example:  '3'
 *
 * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 *
 * 例如，给出 n = 3，生成结果为：
 *
 * [
 * ⁠ "((()))",
 * ⁠ "(()())",
 * ⁠ "(())()",
 * ⁠ "()(())",
 * ⁠ "()()()"
 * ]
 *
 *
 */

// @lc code=start
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        Stack<Character> st = new Stack<>();
        fun(res, sb, 0, n*2, n, n, st);
        return res;
    }

    void fun(List<String> res, StringBuilder sb, int cur, int target,
            int leftNum, int rightNum, Stack<Character> st) {
                if (cur == target) {
                    res.add(sb.toString());
                    return;
                }
                if (rightNum < st.size()) {
                    return;
                }
                if (leftNum > 0) {
                    st.push('(');
                    sb.append('(');

                    fun(res, sb, cur+1, target, leftNum-1, rightNum, st);
                    if (!st.empty())
                        st.pop();
                    sb.deleteCharAt(sb.length()-1);
                }

                if (rightNum > 0) {
                    if( st.isEmpty() || st.peek() != '(') {
                        return;
                    }
                    st.pop();
                    sb.append(')');

                    fun(res, sb, cur+1, target, leftNum, rightNum-1, st);
                    st.push('(');
                    sb.deleteCharAt(sb.length() - 1);
                }

            }
}
// @lc code=end

